﻿购物车内的商品价格按照升序记录于数组 price。
请在购物车中找到两个商品的价格总和刚好是 target。
若存在多种情况，返回任一结果即可。

输入：price = [3, 9, 12, 15], target = 18
输出：[3, 15] 或者[15, 3]

输入：price = [8, 21, 27, 34, 52, 66], target = 61
输出：[27, 34] 或者[34, 27]

	提示：
	1 <= price.length <= 10 ^ 5
	1 <= price[i] <= 10 ^ 6
	1 <= target <= 2 * 10 ^ 6

    // class Solution {
    // public:
    //     vector<int> twoSum(vector<int>& nums, int target) {
    //         int n = nums.size();
    //         for (int i = 0; i < n; i++) { // 第⼀层循环从前往后列举第⼀个数

    //             for (int j = i + 1; j < n;
    //                  j++) { // 第⼆层循环从i位置之后列举第⼆个数已经找到结果了
    //                 if (nums[i] + nums[j] ==
    //                     target) // 两个数的和等于⽬标值，说明我们
    //                     return {nums[i], nums[j]};
    //             }
    //         }
    //         return {-1, -1};
    //     }
    // };

    class Solution {
    public:
        vector<int> twoSum(vector<int>& nums, int target) {
            int left = 0, right = nums.size() - 1;
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum > target)
                    right--;
                else if (sum < target)
                    left++;
                else
                    return { nums[left], nums[right] };
            }
            // 照顾编译器

            return { -4941, -1 };
        }
};